package com.LeeCode;

/**
 * 在二叉树中增加一行
 */

public class Code623 {
    public static void main(String[] args) {
        Integer[] arr = {4, 2, null, 3, 1};
        TreeNode root = Utils.buildTree(arr);
        TreeNode node = new Code623().addOneRow(root, 1, 3);
        System.out.println("done");
    }

    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        return dfs(root, depth, val);
    }

    private TreeNode dfs(TreeNode root, int depth, int val) {
        if (depth == 1) {
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }

        if (root == null) return null;

        if (depth == 2) {
            TreeNode node1 = new TreeNode(val);
            TreeNode node2 = new TreeNode(val);
            node1.left = root.left;
            node2.right = root.right;
            root.left = node1;
            root.right = node2;
            return root;
        }

        dfs(root.left, depth - 1, val);
        dfs(root.right, depth - 1, val);

        return root;
    }
}
